#ifndef PRIME_H
#define PRIME_H

#include <ctime>
class Prime
{
public:
	void GetPrime(int n);
	void GetPrime2(int n);

private:
	void output(int *arr, int start, int end);
};

void Prime::output(int *arr, int start, int end)
{
	for (int i = start; i <= end; ++i)
	{
		if (arr[i])
		{
			cout << i << ' ';
		}
	}
	cout << '\n';
}

void Prime::GetPrime(int n)
{
	int start = clock();

	int *prime = new int[n+1];
	for (int i = 0; i <= n; ++i)
		prime[i] = 1;

	for (int i = 2; i <=n; ++i)
	{
		if (prime[i])
		{
			for (int j = 2; j <= n/i; ++j)
			{
				prime[i*j] = 0;
			}
		}
	}

	cout << "TimeSpan " << clock() - start << '\n';

	output(prime, 2, n);
	delete [] prime;
}


void Prime::GetPrime2(int n)
{
	int start = clock();

	int *prime = new int[n+1];
	for (int i = 2; i <= n; ++i)
	{
		prime[i] = 1;
	}

	for (int i = 2; i*i <= n; ++i)
	{
		if (prime[i] == 1)
		{
			for (int j = 2*i; j <= n; ++j)
			{
				if (j % i == 0)
					prime[j] = 0;
			}
		}
	}

	cout << "TimeSpan " << clock() - start << '\n';

	output(prime, 2, n);
	delete [] prime;
}

#endif